home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 251_01 / advavl.c < prev    next >
Text File  |  1987-10-27  |  4KB  |  194 lines
  1. /* advavl.c - avl tree manipulation routines */
  2. /*
  3.     Copyright (c) 1986, by David Michael Betz
  4.     All rights reserved
  5. */
  6.  
  7. #include "advavl.h"
  8. #include "advdbs.h"
  9.  
  10. #define TRUE    1
  11. #define FALSE    0
  12. #define NULL    0
  13.  
  14. /* external routines */
  15. extern char *save();
  16. extern char *malloc();
  17.  
  18. /* external variables */
  19. extern char *data;
  20. extern int curwrd;
  21. extern int dptr;
  22.  
  23. /* local variables */
  24. static TREE *curtree;
  25. static char thiskey[WRDSIZE+1];
  26.  
  27. /* tnew - allocate a new avl tree */
  28. TREE *tnew()
  29. {
  30.     TREE *tree;
  31.  
  32.     /* allocate the tree structure */
  33.     if ((tree = (TREE *)malloc(sizeof(TREE))) == NULL)
  34.     return (NULL);
  35.  
  36.     /* initialize the new tree */
  37.     tree->tr_root = NULL;
  38.     tree->tr_cnt = 0;
  39.  
  40.     /* return the new tree */
  41.     return (tree);
  42. }
  43.  
  44. /* tenter - add an entry to an avl tree */
  45. int tenter(tree,key)
  46.   TREE *tree; char *key;
  47. {
  48.     int h;
  49.     curtree = tree;
  50.     strncpy(thiskey,key,WRDSIZE); thiskey[WRDSIZE] = 0;
  51.     return (tenter1(&tree->tr_root,&h));
  52. }
  53.  
  54. /* tenter1 - internal insertion routine */
  55. int tenter1(pnode,ph)
  56.   TNODE **pnode; int *ph;
  57. {
  58.     TNODE *p,*q,*r;
  59.     int val,c;
  60.  
  61.     /* check for the subtree being empty */
  62.     if ((p = *pnode) == NULL) {
  63.     if (p = (TNODE *)malloc(sizeof(TNODE))) {
  64.         curtree->tr_cnt++;
  65.         KEY(p) = save(thiskey);
  66.         WORD(p) = curwrd;
  67.         LLINK(p) = RLINK(p) = NULL;
  68.         B(p) = 0;
  69.         *pnode = p;
  70.         *ph = TRUE;
  71.         return (WORD(p));
  72.     }
  73.     else {
  74.         *ph = FALSE;
  75.         return (NIL);
  76.     }
  77.     }
  78.  
  79.     /* otherwise, check for a match at this node */
  80.     else if ((c = strcmp(thiskey,KEY(p))) == 0) {
  81.     *ph = FALSE;
  82.     return (WORD(p));
  83.     }
  84.  
  85.     /* otherwise, check the left subtree */
  86.     else if (c < 0) {
  87.     val = tenter1(&LLINK(p),ph);
  88.     if (*ph)
  89.         switch (B(p)) {
  90.         case 1:
  91.         B(p) = 0;
  92.         *ph = FALSE;
  93.         break;
  94.         case 0:
  95.         B(p) = -1;
  96.         break;
  97.         case -1:
  98.         q = LLINK(p);
  99.         if (B(q) == -1) {
  100.             LLINK(p) = RLINK(q);
  101.             RLINK(q) = p;
  102.             B(p) = 0;
  103.             p = q;
  104.         }
  105.         else {
  106.             r = RLINK(q);
  107.             RLINK(q) = LLINK(r);
  108.             LLINK(r) = q;
  109.             LLINK(p) = RLINK(r);
  110.             RLINK(r) = p;
  111.             B(p) = (B(r) == -1 ?  1 : 0);
  112.             B(q) = (B(r) ==  1 ? -1 : 0);
  113.             p = r;
  114.         }
  115.         B(p) = 0;
  116.         *pnode = p;
  117.         *ph = FALSE;
  118.         break;
  119.         }
  120.     }
  121.  
  122.     /* otherwise, check the right subtree */
  123.     else {
  124.     val = tenter1(&RLINK(p),ph);
  125.     if (*ph)
  126.         switch (B(p)) {
  127.         case -1:
  128.         B(p) = 0;
  129.         *ph = FALSE;
  130.         break;
  131.         case 0:
  132.         B(p) = 1;
  133.         break;
  134.         case 1:
  135.         q = RLINK(p);
  136.         if (B(q) == 1) {
  137.             RLINK(p) = LLINK(q);
  138.             LLINK(q) = p;
  139.             B(p) = 0;
  140.             p = q;
  141.         }
  142.         else {
  143.             r = LLINK(q);
  144.             LLINK(q) = RLINK(r);
  145.             RLINK(r) = q;
  146.             RLINK(p) = LLINK(r);
  147.             LLINK(r) = p;
  148.             B(p) = (B(r) ==  1 ? -1 : 0);
  149.             B(q) = (B(r) == -1 ?  1 : 0);
  150.             p = r;
  151.         }
  152.         B(p) = 0;
  153.         *pnode = p;
  154.         *ph = FALSE;
  155.         break;
  156.         }
  157.     }
  158.  
  159.     /* return the node found or inserted */
  160.     return (val);
  161. }
  162.  
  163. /* tfind - find an entry in an avl tree */
  164. int tfind(tree,key)
  165.   TREE *tree; char *key;
  166. {
  167.     strncpy(thiskey,key,WRDSIZE); thiskey[WRDSIZE] = 0;
  168.     return (tfind1(tree->tr_root));
  169. }
  170.  
  171. /* tfind1 - internal lookup routine */
  172. int tfind1(node)
  173.   TNODE *node;
  174. {
  175.     int c;
  176.  
  177.     /* check for the subtree being empty */
  178.     if (node == NULL)
  179.     return (NIL);
  180.  
  181.     /* otherwise, check for a match at this node */
  182.     else if ((c = strcmp(thiskey,KEY(node))) == 0)
  183.     return (WORD(node));
  184.  
  185.     /* otherwise, check the left subtree */
  186.     else if (c < 0)
  187.     return (tfind1(LLINK(node)));
  188.  
  189.     /* otherwise, check the right subtree */
  190.     else
  191.     return (tfind1(RLINK(node)));
  192. }
  193. 
  194.